1. Field of the Invention
This invention relates to the field of Optimizing Compilers for computer systems. More specifically, the invention is an improved method and apparatus for allocating live variables to available Central Processing Unit ("CPU") registers during the code optimization pass of an optimizing compiler.
2. Background
It is desirable that computer programs be as efficient as possible in their execution time and memory usage. This need has spawned the development of optimizing compilers. Optimizing compilers typically contain a Code Optimization section which sits between a compiler front end and a compiler back end. The Code Optimization section takes as input the "intermediate code" output by the compiler front end, and operates on this code to perform various transformations to it which will result in a faster and more efficient target program. The transformed code is passed to the compiler back end which then converts the code to a binary version for the particular machine involved (i.e. SPARC, X86, IBM, etc). The Code Optimization section itself needs to be as fast and memory efficient as it possibly can be.
For example, most code optimization sections attempt to optimize the usage of the available CPU registers in the target computer. This is done by determining a "live variable set" for the target program using graphing and flow control techniques and rearranging the program code to minimize the number of variables which must be "spilled" into memory from the registers during program execution. This register allocation process involves operating on hundreds of variables in the average target program being compiled and could involve 10 to 20 thousand variables in scientific target programs. Thus in processing this large number of target program variables the code optimizer itself could be excessively time consuming and use memory excessively in making these register allocation calculations if it does not handle the optimizing calculations properly.
In the past, attempts have been made to develop optimizing compilers generally, and code optimizer modules specifically which themselves run as efficiently as possible. A general discussion of optimizing compilers and the related techniques used can be found in the text book "Compilers: Principles, Techniques and Tools" by Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman, Addison-Wesley Publishing Co 1988, ISBN 0-201-10088-6, especially chapters 9 & 10 pages 513-723. One such attempt at reducing the calculation time of the code optimizer was to reduce the time for calculating "live variable sets" in the register allocation process. Normally, the calculation of the live variables in a control flow graph involves N.sup.2 calculations and memory storage space, where N=the number of variables involved. In this attempt at reducing calculation time, an approach to finding the "live variable set" involved the construction of the target's static single assignment ("SSA") graph and the insertion in the graph of special definitions called ".PHI. functions" or ".PHI.-nodes" at those points where control-flow paths join and different values merge. This method reduced the calculations for the number of variables from N.sup.2 to N, a significant reduction in time and memory usage. This method is described in "Register Allocation via Graph Coloring" by Preston Briggs, PhD. thesis, Rice University April, 1992 which is incorporated herein by reference. However, this method of Briggs produces more variable "spilling" than necessary by making it appear that some variables in the "live set" cannot co-exist in the registers with other variables (thus causing them to spill into memory) when in fact they can.
The present invention uses an elegant method to reduce these erroneous variable spills thereby increasing the target program efficiency with no loss in efficiency in the code optimizer itself.